#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void print(int*a,int size)
{
for (int i = 0; i < size; i++)
{
    printf("%d ",a[i]);
}
printf("\n");

}

void Swap(int*a,int*b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void Bubblesort(int*a,int size)
{   
    for (int i = 0; i<size-1; i++)
    {
       int flag=0;
    for (int j = 0; j<size-i-1; j++)
    {
        if (a[j]>a[j+1])
        {   flag=1;
             Swap(&a[j],&a[j+1]);
        }
        
        
    } 
    if(flag==0)
    {
        break;
    }
        
    }
    


}

void InsertSort(int*a,int size)
{
    for (int  i = 0; i < size; i++)
    {   int j=i;//i是要插入的数据的下标
        int temp=a[i];
        for (; j >0; j--)
        {
            if (a[j-1]>temp)
            {
                a[j]=a[j-1];
            }
            else
            {
                break;
            }
            
        }
        
    a[j]=temp;
    }
}

void ChooseSort2(int*a,int size)
{
    for (int i = 0; i < size-1; i++)
    {
        int min=i;
        for (int j = i+1; j<size ; j++)
        {
        if (a[min]>a[j])
        {
            min=j;
        }
        }
        Swap(&a[i],&a[min]);
    }
    


}
//双指针
void ChooseSort(int*a,int size)
{
    for (int left= 0,right=size-1; left<right; left++,right--)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if (a[min]>a[i])
            {
                min=i;
            }
            if (a[max]<a[i])
            {
                max=i;
            }
            
        }
        Swap(&a[left],&a[min]);
        //极值正好在两边
        if (max==left)
        {
            max=min;
        }
        
        Swap(&a[right],&a[max]);
    }
    


}

//快速排序:双指针  分治 递归
void FastSort(int*a,int start,int end)
{
    if (start>=end)
    {
        return;
    }
    int left=start;
    int right=end;
    int temp=a[left];
      
    while (left<right)
    {
        //先右边动,找比基准值小
        while (a[right]>temp&&left<right)
        {
            right--;
        }
         //把右边的值赋给左边空位
        if(left<right)
        {
            a[left++]=a[right];
        }
        while (a[left]<temp&&left<right)
        {
            left++;
        }
        if(left<right)
        a[right--]=a[left];

    }
    a[left]=temp;
    FastSort(a,start,left-1);
    FastSort(a,left+1,end);





}



int main()
{
    int a[5];
    srand(time(NULL));
    for (int i = 0; i < 5; i++)
    {
        a[i]=rand()%100+1;
    }
    
    print(a,sizeof(a)/sizeof(a[0]));
    

    FastSort(a,0,4);
    print(a,sizeof(a)/sizeof(a[0]));
    return 0;

}